package selectionSort;

/**
 * Created with IntelliJ IDEA.
 * Description: 直接选择排序
 * User: 86187
 * Date: 2022-08-10
 * Time: 14:09
 */

public class MySelectionSort {

    /**
     *  选择排序:
     *  时间复杂度: O(N^2)
     *  空间复杂度：O(1)
     *  稳定性: 不稳定
     */
    //每次选最小的放到前面
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i+1;j < array.length;++j) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            //交换
            swap(array,minIndex,i);
        }
    }
    public static void swap(int[] array,int minIndex,int i) {
        int tmp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = tmp;
    }

    /**
     *  优化后:
     *  每次选两个数据:一大一小，小的放前，大的放后
     *  时间复杂度：O(N^2)
     */
    public static void selectionSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int index = left+1; index <= right; index++) {
                if(array[index] < array[minIndex]) {
                    minIndex = index;
                }
                if(array[index] > array[maxIndex]) {
                    maxIndex = index;
                }
            }
            swap(array,left,minIndex);
            if(left == maxIndex) {
                //防止上一步的交换函数篡改了找到的最大值
                //可用[18,3,10,2,7]这个例子来画图理解
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
}
